Assigning traffic flows to paths in a network is a complex problem. There are multiple attributes associated with the nodes and links and multiple constraints to be satisfied. Networks of large numbers of nodes, links and flows can provide an enormous number of flow-to-path assignments. Traffic Engineering (TE) in a network is a process of controlling the flows of data packets through the network to optimize the utilization of network resources (e.g., routers, switches, etc.) and to improve the network performance. Traffic engineering selects communication paths in a network to use the network bandwidth efficiently thereby avoiding a situation in which some network resources are overutilized and others are underutilized.
Constraint-Based Routing (CBR) is a TE mechanism for computing a feasible network path based on a traffic description and a set of constraints. While conventional IP routing algorithms (e.g., Bellman-Ford, Dijkstra) find a path that optimizes a scalar metric (e.g., number of hops), CBR finds a path that optimizes a scalar metric and does not violate a set of constraints. For example, link bandwidth may be a constraint in a sense that each of the links in a path selected by the algorithm must have a certain minimum available bandwidth. Administrative policy may be another constraint. A policy may specify that certain traffic may be blocked on some nodes and links or restricted to some nodes and links. CBR may also include a combination of bandwidth and administration policy.
A CBR system may use Multiprotocol Label Switching (MPLS) as a forwarding mechanism. MPLS is an advanced forwarding scheme that extends routing with respect to packet forwarding and path controlling thereby enabling TE. Each MPLS packet has a header that contains labels. Label Switching Routers (LSRs) in a MPLS network examine these labels and make forwarding decisions based on these values. This operation can be done much faster than conventional IP forwarding because it is not necessary to perform a longest prefix match between the destination IP address and the data in the forwarding table as is required in conventional IP forwarding. Instead, label-forwarding tables indicate how incoming packets are processed. Specifically, these tables indicate how to change the label of a packet arriving on one interface before that packet is transmitted on a different interface.
In an MPLS system, packet processing is much faster than conventional IP forwarding and several different paths can be established to route packets from source to destination. Forwarding is no longer limited to destination-based, hop-by-hop decisions. Administrative policy or TE can be used to explicitly define paths for flows in a MPLS system. Furthermore, the assignment of a flow to a path can use complex algorithms without affecting all the LSRs that simply forward packets. The techniques of MPLS are not limited to Internet Protocol (IP) and are applicable to any network layer protocol (e.g., Appletalk, IPX).
Resource Reservation Protocol (RSVP) is a protocol that can be implemented in a MPLS network and provides a general facility for reserving resources for a flow. The quality-of-service (QoS) requirements for a flow determine the resources that must be reserved at each network element along the path assigned to that flow. RSVP operates by using path messages and resv messages. Path messages are transmitted from sender to receiver through intermediate routers. Each router that receives a path message inserts its own IP address in the message before forwarding it to the next router. This design allows any router that receives a path message to know the path back to the sender. A path message also contains information about the traffic characteristics of a flow. Resv messages are transmitted from receiver to sender and reserve the resources that are required for the flow.
Because of the complexity of most communication networks and the infinite number of scenarios of possible traffic patterns on these networks, it is not possible to evaluate all possible routing options within a reasonable period of time. While the above methods are effective in making network routing decisions, methods that have been used to solve other types of complex problems may be adapted to be used to solve network routing issues. For example, genetic algorithms have been used in many types of applications to provide evolutionary search techniques to identify optimal solutions for various applications that encompass complex problems. Genetic algorithms use an iterative refinement technique that evaluates whether one solution is better than another. Further information about genetic algorithms is available in Handbook of Genetic Algorithms, Lawrence Davis, Van Nostrand Reinhold, 1991. It is contemplated that applying genetic algorithms to a constraint-based routing scheme may result in a more effective routing mechanism than the current TE techniques.